Maximum Non Negative Product in a Matrix

算是个简单的DP, 扫一遍就行，用滚动数组可以优化空间复杂度到On，这里比较粗暴。On^2&On^2

impl Solution {
    pub fn max_product_path(grid: Vec<Vec<i32>>) -> i32 {
        use std::cmp::max;
        
        let mut posi: Vec<Vec<i64>> = vec![vec![-1;grid[0].len()];grid.len()];
        let mut nega: Vec<Vec<i64>> = posi.clone();
        if grid[0][0] >= 0 {
            posi[0][0] = grid[0][0] as i64;
        } else {
            nega[0][0] = -grid[0][0] as i64;
        }
        for i in 1..grid.len() {
            if grid[i][0] >= 0 {
                posi[i][0] = get_mul(posi[i-1][0], grid[i][0]);
                nega[i][0] = get_mul(nega[i-1][0], grid[i][0]);
            } else {
                nega[i][0] = get_mul(posi[i-1][0], -grid[i][0]);
                posi[i][0] = get_mul(nega[i-1][0], -grid[i][0]);
            }
        }
        for i in 1..grid[0].len() {
            if grid[0][i] >= 0 {
                posi[0][i] = get_mul(posi[0][i-1], grid[0][i]);
                nega[0][i] = get_mul(nega[0][i-1], grid[0][i]);
            } else {
                nega[0][i] = get_mul(posi[0][i-1], -grid[0][i]);
                posi[0][i] = get_mul(nega[0][i-1], -grid[0][i]);
            }
        }
        for i in 1..grid.len() {
            for j in 1..grid[0].len() {
                if grid[i][j] >= 0 {
                    posi[i][j] = get_mul(max(posi[i-1][j], posi[i][j-1]), grid[i][j]);
                    nega[i][j] = get_mul(max(nega[i-1][j], nega[i][j-1]), grid[i][j]);
                } else {
                    nega[i][j] = get_mul(max(posi[i-1][j], posi[i][j-1]), -grid[i][j]);
                    posi[i][j] = get_mul(max(nega[i-1][j], nega[i][j-1]), -grid[i][j]);
                }
            }
        }

        let res = posi[grid.len()-1][grid[0].len()-1] % 1000000007;
        if res < 0 {
            for i in 0..grid.len() {
                for j in 0..grid[0].len() {
                    if grid[i][j] == 0 {
                        return 0;
                    }
                }
            }
        }
        res as i32
    }
}

fn get_mul(x: i64, y: i32) -> i64 {
    if x == -1 {
        -1
    } else {
        x * y as i64
    }
}